public class HorseStep {  
      
    public static int X = 8;  
    public static int Y = 8;  
      
    public static int returnCount = 0;  
      
    /** 
     * 棋盘 
     */  
    public static int chess[][] = new int[X][Y];  
      
      
    /** 
     * 找到基于（x,y）位置的下一个可走位置 
     * @param x 
     * @param y 
     * @param count 
     * @return 
     */  
    public static int nextxy(XY xy,int count){  
          
        final int a=0,  
                b=1,  
                c=2,  
                d=3,  
                e=4,  
                f=5,  
                g=6,  
                h=7;  
          
        int x = xy.getX();  
        int y = xy.getY();  
          
        int returnInt = 0;  
          
        switch (count) {  
          
//      从以x,y为轴心的 右下 开始  
          
        case a:  
            if( x+2<=X-1 && y+1<=Y-1 && chess[y+1][x+2]==0){  
                x +=2;  
                y +=1;  
                returnInt = 1;  
            }  
              
            break;  
              
        case b:  
            if( x+1<=X-1 && y+2<=Y-1 && chess[y+2][x+1]==0){  
                x +=1;  
                y +=2;  
                returnInt = 1;  
            }  
              
            break;  
              
        case c:  
            if( x-1>=0 && y+2<=Y-1 && chess[y+2][x-1]==0){  
                x -=1;  
                y +=2;  
                returnInt = 1;  
            }  
              
            break;  
              
        case d:  
            if( x-2>=0 && y+1<=Y-1 && chess[y+1][x-2]==0){  
                x -=2;  
                y +=1;  
                returnInt = 1;  
            }  
              
            break;  
          
        case e:  
            if( x-2>=0 && y-1>=0 && chess[y-1][x-2]==0){  
                x -=2;  
                y -=1;  
                returnInt = 1;  
            }  
              
            break;  
              
        case f:  
            if( x-1>=0 && y-2>=0 && chess[y-2][x-1]==0){  
                x -=1;  
                y -=2;  
                returnInt = 1;  
            }  
              
            break;  
              
        case g:  
            if( x+1<=X-1 && y-2>=0 && chess[y-2][x+1]==0){  
                x +=1;  
                y -=2;  
                returnInt = 1;  
            }  
              
            break;  
              
        case h:  
            if( x+2<=X-1 && y-1>=0 && chess[y-1][x+2]==0){  
                x +=2;  
                y -=1;  
                  
                returnInt = 1;  
            }  
            break;  
              
        default:  
            break;  
        }  
          
        if(returnInt == 1){  
            xy.setX(x);  
            xy.setY(y);  
              
            return 1;  
        }  
  
        return 0;  
    }  
      
    /** 
     * 打印棋盘 
     */  
    public static void print(){  
        for(int i=0;i<X;i++){  
            for(int j=0;j<Y;j++){  
                  
                if(chess[i][j]<10)  
                    System.out.print(chess[i][j]+"  ");  
                else  
                    System.out.print(chess[i][j]+" ");  
                  
            }  
            System.out.println();  
        }  
          
    }  
      
    /** 
     * 深度优先遍历棋盘 
     * @param x 
     * @param y 
     * @param tag 
     * @return 
     * （x,y)为位置坐标 
     * tag是标记变量，每走一步 tag+1。 
     */  
    public static int TravelChessBoard(XY xy,int tag){  
          
//      马在某个点有八种可能的方向，用来约束查找小于八种的变量  
        Integer count = 0;  
          
//      马所在位置是否可以再跳向下一个位置，0有，1无（条件：1，不出边界，2.没有走过）  
        int haveNextXy = 0;  
          
        int x = xy.getX();  
        int y = xy.getY();  
          
//      x是横轴，y是竖轴，左上角为0,0点，往右和往下递增  
        chess[y][x] = tag;  
          
//      最后一步，递归的终止条件  
        if(X*Y == tag){  
//          打印棋盘  
            print();  
            return 1;  
        }  
          
//      找到马的下一个可走坐标（x1,y1)，如果找到为1，否则为0.  
        haveNextXy = nextxy(xy, count);  
          
        while( 0==haveNextXy && count<7){  
            count ++;  
            haveNextXy = nextxy(xy, count);  
        }  
          
        while(haveNextXy==1){  
            if(TravelChessBoard(xy, tag+1)==1){  
                return 1;  
            }  
              
//          回退后，把当前点也设置为回退后的位置  
            xy.setX(x);  
            xy.setY(y);  
              
            count++;  
              
//          找到马的下一个可走坐标（x1,y1)，如果找到flag=1，否则为0.  
            haveNextXy = nextxy(xy, count);  
              
            while( 0==haveNextXy && count<7){  
                count ++;  
                haveNextXy = nextxy(xy, count);  
            }  
        }  
          
//      回退  
        if(haveNextXy==0){  
            chess[y][x]=0;  
            returnCount++;  
        }  
          
        return 0 ;  
    }  
      
    public static void main(String[] args) {  
        long begin = System.currentTimeMillis();  
          
//      马所在位置的坐标，x是横轴，y是竖轴，左上角为0,0点，往右和往下递增  
        XY xy = new XY();  
        xy.setX(1);  
        xy.setY(0);  
          
        if(TravelChessBoard(xy, 1)==0){  
            System.out.println("马踏棋盘失败");  
        }  
          
        long time = System.currentTimeMillis()-begin;  
          
        System.out.println("耗时"+time+"毫秒");  
        System.out.println(returnCount);  
    }  
      
}  
  
  
class XY{  
    private int x;  
    private int y;  
    public int getX() {  
        return x;  
    }  
    public void setX(int x) {  
        this.x = x;  
    }  
    public int getY() {  
        return y;  
    }  
    public void setY(int y) {  
        this.y = y;  
    }  
      
      
}  
